import geopandas as gpd
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np

pd.set_option('display.max_columns', 500)

S = 8000

# Note: it might take time, as FD is a huge file.

FDs = gpd.read_file("Data/California_Fire_Districts.shp") # load a shapefile containing California Fire District here
blocks = gpd.read_file("Data/sbBlocks_pop.shp") # Load a shapefile containing Santa Barbara County blocks here
stations = gpd.read_file("Data/Fire_Stations_SBC.shp") # Load a shapefile containing Fire Stations in Santa Barbara County here

blocks = blocks.to_crs("epsg:3310") 

stations = stations.to_crs("epsg:3310")

FDs.plot("Name")

<Axes: >

FDs = FDs.loc[FDs.intersects(blocks.unary_union)].reset_index(drop=True)
FDs.plot("Name", legend=True, figsize=(10,10))

<Axes: >

#FDs.crs

#blocks.crs

#stations.crs

FDs

SBC_FD = FDs.loc[FDs["Name"] == "SANTA BARBARA CFD"].reset_index() ##PUT YOUR ANSWER HERE##

SBC_FD

#SBC_FD.plot()

del FDs

stations

stations = stations.loc[stations.within(SBC_FD.unary_union)].reset_index()
#stations.loc[stations["Department"].isin(["Santa Barbara County Fire Department"])].reset_index()

len(stations)

28

len(blocks)

7258

from matplotlib_scalebar.scalebar import ScaleBar

#blocks.centroid.plot(ax=A, markersize=blocks.elpop * 2, color="orange", label="Block Centroids")  

blocks["geometry"] = blocks["geometry"].centroid

blocks = blocks.loc[blocks.within(SBC_FD.unary_union.buffer(10))].reset_index()

blocks["Population"].max()

2598

blocks = blocks.loc[blocks["Population"] > 0].reset_index()

A = stations.plot(color="red", zorder = 10, markersize = 10)

blocks.plot("Population", legend=True, figsize=(10,10), ax=A, markersize=blocks["Population"]/2, cmap = "summer", alpha = 0.4)
plt.title("Block Population and Stations in Santa Barbara CFD")

scalebar = ScaleBar(dx=1, scale_formatter=lambda data, unit: f'{data}000 m', length_fraction=0.25)
A.add_artist(scalebar)

<matplotlib_scalebar.scalebar.ScaleBar at 0x167415750>

I = len(blocks)
J = len (stations)
P = 20

a_i = blocks["Population"]

D_ij = [[np.sqrt((blocks.geometry.centroid.x[i] - stations.geometry.x[j])**2 + (blocks.geometry.centroid.y[i] - stations.geometry.y[j])**2)
         for j in range(J)] for i in range (I)]

# This is a hint for students who want to do it with list comprehension


# Creating a two-dimensional list
matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9],
          [10, 11, 12]]

# Using list comprehension to filter even numbers from the matrix
# The '%' symbol in Python is called the modulo operator. 
    #It returns the remainder of the division of the left operand by the right operand.
even_numbers = [[matrix[r][c] for c in range(len(matrix[0])) if matrix[r][c]%2 == 0]
                for r in range(len(matrix))]

print(even_numbers)

[[2], [4, 6], [8], [10, 12]]

np.array(D_ij).shape, (I,J)

((1965, 28), (1965, 28))

D_ij = np.array(D_ij)

N_i = [[j for j in range(len(D_ij[0])) if D_ij[i, j] <= 8000]
       for i in range (len(D_ij))]

#N_i

import gurobipy as gp
from gurobipy import GRB

# Create a new Gurobi model
mclp = gp.Model("Maximal_Covering_Location")

# Decision Variables
x = mclp.addVars(J, vtype=GRB.BINARY, name="x")  # Facility is open or not
y = mclp.addVars(I, vtype=GRB.BINARY, name="y")   # Demand is covered or not

# Objective Function
mclp.setObjective((gp.quicksum(a_i[i] * y[i] for i in range (I))), GRB.MAXIMIZE)

# Constraints
# Each demand must be covered by neighboring facility
mclp.addConstrs((gp.quicksum(x[j] for j in N_i[i]) >= y[i] for i in range(I)))


# Number of opened facilities must not exceed P
mclp.addConstr((gp.quicksum(x[j] for j in range(J))) == P)

# Optimize the model
mclp.optimize()

Set parameter Username
Academic license - for non-commercial use only - expires 2025-05-10
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x6f090930
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 128757.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.01s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 167416.00000

Root relaxation: objective 1.676190e+05, 8 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167619.00000 167619.000  0.00%     -    0s

Explored 1 nodes (8 simplex iterations) in 0.08 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167619 167416 128757 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%

stations["selected"] = [x[j].x > 0.5 for j in range(len(stations))]
open_stations = stations.loc[stations["selected"]].reset_index(drop=True)

len(open_stations)

20

A = open_stations.plot(color="red", zorder = 10, markersize = 10)
open_stations.buffer(S).plot(ax=A, edgecolor="red", facecolor="None", linestyle="dashed")

blocks.plot("Population", legend=True, figsize=(10,10), ax=A, markersize=blocks["Population"]/2, cmap = "summer", alpha = 0.4)
plt.title("Block Population and Stations in Santa Barbara CFD")

scalebar = ScaleBar(dx=1, scale_formatter=lambda data, unit: f'{data}000 m', length_fraction=0.25)
A.add_artist(scalebar)

<matplotlib_scalebar.scalebar.ScaleBar at 0x168951cd0>

# Let me give you functionize example.
# For more, refer to Lab 0.

sample_list = [1,2,3,4]

def sum_array(a):
    s = 0
    a = np.array(a)
    for num in a:
        s += num
    return s, a # Return the summation of all elements, and the original array

sum_array(sample_list)

(10, array([1, 2, 3, 4]))

## PUT YOUR FUNCTION HERE!!!##

def solve_mclp(P):
    P = P
    import gurobipy as gp
    from gurobipy import GRB

    # Create a new Gurobi model
    mclp = gp.Model("Maximal_Covering_Location")

    # Decision Variables
    x = mclp.addVars(J, vtype=GRB.BINARY, name="x")  # Facility is open or not
    y = mclp.addVars(I, vtype=GRB.BINARY, name="y")   # Demand is covered or not

    # Objective Function
    mclp.setObjective((gp.quicksum(a_i[i] * y[i] for i in range (I))), GRB.MAXIMIZE)

    # Constraints
    # Each demand must be covered by neighboring facility
    mclp.addConstrs((gp.quicksum(x[j] for j in N_i[i]) >= y[i] for i in range(I)))


    # Number of opened facilities must not exceed P
    mclp.addConstr((gp.quicksum(x[j] for j in range(J))) == P)

    # Optimize the model
    mclp.optimize()
    
    stations["selected"] = [x[j].x > 0.5 for j in range(len(stations))]
    open_stations = stations.loc[stations["selected"]].reset_index(drop=True)


    return open_stations, mclp.obj_val

#solve_mclp(5)

stations_coverage = stations.buffer(S)

total_stations_coverage = stations_coverage.unary_union

blocks_within_coverage = blocks[blocks.geometry.within(total_stations_coverage)]

population_subset = blocks_within_coverage['Population']

current_coverage = population_subset.sum()

current_coverage

167619

selecteds = []  # List to store selected stations for each value of p
obj_vals = []   # List to store objective values for each value of p

# Iterate over values of p starting from 3
for p in range(3, len(stations)+1):
    print(f"=================== for P={p}")  # Print current value of p
    # Call solve_mclp function to solve the problem for current value of p
    selected_stations, obj_val = solve_mclp(p)
    # Append selected stations to the selecteds list
    selecteds.append(selected_stations)
    # Append objective value to the obj_vals list
    obj_vals.append(obj_val)

=================== for P=3
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xe8181d39
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [3e+00, 3e+00]
Found heuristic solution: objective 92175.000000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 94338.000000

Root relaxation: objective 1.420590e+05, 36 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    142059.00000 142059.000  0.00%     -    0s

Explored 1 nodes (36 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 142059 94338 92175 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.420590000000e+05, best bound 1.420590000000e+05, gap 0.0000%
=================== for P=4
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x0162568a
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [4e+00, 4e+00]
Found heuristic solution: objective 92175.000000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 129507.00000

Root relaxation: objective 1.536120e+05, 33 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    153612.00000 153612.000  0.00%     -    0s

Explored 1 nodes (33 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 153612 129507 92175 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.536120000000e+05, best bound 1.536120000000e+05, gap 0.0000%
=================== for P=5
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x31882cce
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [5e+00, 5e+00]
Found heuristic solution: objective 93253.000000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 130073.00000

Root relaxation: objective 1.578840e+05, 28 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    157884.00000 157884.000  0.00%     -    0s

Explored 1 nodes (28 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 157884 130073 93253 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.578840000000e+05, best bound 1.578840000000e+05, gap 0.0000%
=================== for P=6
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x72cbbd19
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [6e+00, 6e+00]
Found heuristic solution: objective 93491.000000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.01s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 130311.00000

Root relaxation: objective 1.615770e+05, 26 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    161577.00000 161577.000  0.00%     -    0s

Explored 1 nodes (26 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 161577 130311 93491 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.615770000000e+05, best bound 1.615770000000e+05, gap 0.0000%
=================== for P=7
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xed8b0a7b
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [7e+00, 7e+00]
Found heuristic solution: objective 93491.000000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 145336.00000

Root relaxation: objective 1.637110e+05, 23 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    163711.00000 163711.000  0.00%     -    0s

Explored 1 nodes (23 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 163711 145336 93491 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.637110000000e+05, best bound 1.637110000000e+05, gap 0.0000%
=================== for P=8
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x6fba2f2b
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [8e+00, 8e+00]
Found heuristic solution: objective 108080.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 145576.00000

Root relaxation: objective 1.657080e+05, 24 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    165708.00000 165708.000  0.00%     -    0s

Explored 1 nodes (24 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 165708 145576 108080 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.657080000000e+05, best bound 1.657080000000e+05, gap 0.0000%
=================== for P=9
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x7035f7b6
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [9e+00, 9e+00]
Found heuristic solution: objective 119589.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 156952.00000

Root relaxation: objective 1.663460e+05, 24 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    166346.00000 166346.000  0.00%     -    0s

Explored 1 nodes (24 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 166346 156952 119589 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.663460000000e+05, best bound 1.663460000000e+05, gap 0.0000%
=================== for P=10
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xd11c01cd
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 119589.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 157042.00000

Root relaxation: objective 1.669120e+05, 19 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    166912.00000 166912.000  0.00%     -    0s

Explored 1 nodes (19 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 166912 157042 119589 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.669120000000e+05, best bound 1.669120000000e+05, gap 0.0000%
=================== for P=11
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x7af76ba8
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 119589.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 157074.00000

Root relaxation: objective 1.671520e+05, 18 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167152.00000 167152.000  0.00%     -    0s

Explored 1 nodes (18 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167152 157074 119589 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.671520000000e+05, best bound 1.671520000000e+05, gap 0.0000%
=================== for P=12
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x4fa1b3b5
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 119658.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 157103.00000

Root relaxation: objective 1.673460e+05, 10 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167346.00000 167346.000  0.00%     -    0s

Explored 1 nodes (10 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167346 157103 119658 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.673460000000e+05, best bound 1.673460000000e+05, gap 0.0000%
=================== for P=13
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x1729feb8
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 125468.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 162548.00000

Root relaxation: objective 1.674650e+05, 10 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167465.00000 167465.000  0.00%     -    0s

Explored 1 nodes (10 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167465 162548 125468 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.674650000000e+05, best bound 1.674650000000e+05, gap 0.0000%
=================== for P=14
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x27935a42
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 126106.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.01s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 162548.00000

Root relaxation: objective 1.675350e+05, 8 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167535.00000 167535.000  0.00%     -    0s

Explored 1 nodes (8 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167535 162548 126106 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.675350000000e+05, best bound 1.675350000000e+05, gap 0.0000%
=================== for P=15
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x4d7e2f36
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 128228.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 163186.00000

Root relaxation: objective 1.676040e+05, 4 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167604.00000 167604.000  0.00%     -    0s

Explored 1 nodes (4 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167604 163186 128228 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676040000000e+05, best bound 1.676040000000e+05, gap 0.0000%
=================== for P=16
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xc1d2ab13
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 128336.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 163186.00000

Root relaxation: objective 1.676180e+05, 5 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167618.00000 167618.000  0.00%     -    0s

Explored 1 nodes (5 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167618 163186 128336 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676180000000e+05, best bound 1.676180000000e+05, gap 0.0000%
=================== for P=17
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xaeb6fde8
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 128365.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 166879.00000

Root relaxation: objective 1.676190e+05, 4 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167619.00000 167619.000  0.00%     -    0s

Explored 1 nodes (4 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167619 166879 128365 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%
=================== for P=18
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xc9f32491
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 128365.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 166879.00000

Root relaxation: objective 1.676190e+05, 4 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167619.00000 167619.000  0.00%     -    0s

Explored 1 nodes (4 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167619 166879 128365 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%
=================== for P=19
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x32d7c1da
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 128687.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.01s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 167402.00000

Root relaxation: objective 1.676190e+05, 6 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167619.00000 167619.000  0.00%     -    0s

Explored 1 nodes (6 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167619 167402 128687 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%
=================== for P=20
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x6f090930
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 128757.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 167416.00000

Root relaxation: objective 1.676190e+05, 8 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167619.00000 167619.000  0.00%     -    0s

Explored 1 nodes (8 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167619 167416 128757 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%
=================== for P=21
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xac483780
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 128757.00000
Presolve removed 1929 rows and 1930 columns
Presolve time: 0.01s
Presolved: 37 rows, 63 columns, 186 nonzeros
Variable types: 0 continuous, 63 integer (62 binary)
Found heuristic solution: objective 167133.00000

Root relaxation: objective 1.676190e+05, 9 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167619.00000 167619.000  0.00%     -    0s

Explored 1 nodes (9 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167619 167133 128757 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%
=================== for P=22
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x7f56a9df
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 132450.00000
Presolve removed 1931 rows and 1933 columns
Presolve time: 0.01s
Presolved: 35 rows, 60 columns, 164 nonzeros
Variable types: 0 continuous, 60 integer (58 binary)
Found heuristic solution: objective 167485.00000

Root relaxation: objective 1.676190e+05, 9 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167619.00000 167619.000  0.00%     -    0s

Explored 1 nodes (9 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167619 167485 132450 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%
=================== for P=23
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x2c5ff2db
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 132450.00000
Presolve removed 1934 rows and 1938 columns
Presolve time: 0.00s
Presolved: 32 rows, 55 columns, 138 nonzeros
Variable types: 0 continuous, 55 integer (52 binary)
Found heuristic solution: objective 167618.00000

Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 2: 167618 132450 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676180000000e+05, best bound 1.676190000000e+05, gap 0.0006%
=================== for P=24
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xca8093f1
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 132451.00000
Presolve removed 1938 rows and 1943 columns
Presolve time: 0.00s
Presolved: 28 rows, 50 columns, 116 nonzeros
Variable types: 0 continuous, 50 integer (47 binary)
Found heuristic solution: objective 167619.00000

Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 2: 167619 132451 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%
=================== for P=25
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x47935a47
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [2e+01, 2e+01]
Found heuristic solution: objective 132936.00000
Presolve removed 1966 rows and 1993 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 1 (of 8 available processors)

Solution count 2: 167619 132936 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%
=================== for P=26
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xfd04765c
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [3e+01, 3e+01]
Found heuristic solution: objective 165598.00000
Presolve removed 1966 rows and 1993 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 8 available processors)

Solution count 2: 167619 165598 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%
=================== for P=27
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x82e57cf4
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [3e+01, 3e+01]
Found heuristic solution: objective 165598.00000
Presolve removed 1966 rows and 1993 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 1 (of 8 available processors)

Solution count 2: 167619 165598 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%
=================== for P=28
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x91f973c1
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [3e+01, 3e+01]
Found heuristic solution: objective 167619.00000
Presolve removed 1966 rows and 1993 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 8 available processors)

Solution count 1: 167619 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.676190000000e+05, best bound 1.676190000000e+05, gap 0.0000%

results = pd.DataFrame({
    'P': range(3, len(stations)+1),
    'Coverage': obj_vals
})
results

def scatterplot_result(results):
    # Plot the DataFrame, in scatter plot, taking P values as x and Coverage values as y
    results.plot(kind="scatter", x="P", y="Coverage")
    # Add grid lines
    plt.grid(True)
    # Add the current coverage point in color red
    plt.scatter(len(stations), current_coverage, color="red")
    # provide a dashed red line to inform current coverage
    plt.axhline(y=current_coverage, color='r', linestyle='--', label='Current Coverage')
    # show the plot!
    plt.show()
    
scatterplot_result(results)

def map_result(p, demand_block=True):
    open_stations = selecteds[p-3]
    ## PUT YOUR ANSWER HERE ##

    A = open_stations.plot(color="red", zorder = 10, markersize = 10)
    open_stations.buffer(S).plot(ax=A, edgecolor="red", facecolor="None", linestyle="dashed")

    blocks.plot("Population", legend=True, figsize=(10,10), ax=A, markersize=blocks["Population"]/2, cmap = "summer", alpha = 0.4)
    plt.title("Block Population and Stations in Santa Barbara CFD")

    scalebar = ScaleBar(dx=1, scale_formatter=lambda data, unit: f'{data}000 m', length_fraction=0.25)
    A.add_artist(scalebar)
    
    if demand_block:
        blocks.plot("Population", ax=A, legend=True, markersize=5)
    else:
        fishnet_points.plot(ax=A)
    plt.title(f"{p} stations open")
    plt.show()
    
map_result(14) # Try different p!

def optimize_and_evaluate(demand_block=True):
    selecteds = [] 
    obj_vals = [] 
    for p in range(3, len(stations)+1):
        print(f"=================== for P={p}")
        selected_stations, obj_val = solve_mclp(p)
        selecteds.append(selected_stations)
        obj_vals.append(obj_val)
        map_result(p, demand_block)
        
    results = pd.DataFrame({
        'P': range(3, len(stations)+1),
        'Coverage': obj_vals
    })
    scatterplot_result(results)

optimize_and_evaluate()

=================== for P=3
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xe8181d39
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [3e+00, 3e+00]
Found heuristic solution: objective 92175.000000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 94338.000000

Root relaxation: objective 1.420590e+05, 36 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    142059.00000 142059.000  0.00%     -    0s

Explored 1 nodes (36 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 142059 94338 92175 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.420590000000e+05, best bound 1.420590000000e+05, gap 0.0000%

=================== for P=4
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x0162568a
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [4e+00, 4e+00]
Found heuristic solution: objective 92175.000000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 129507.00000

Root relaxation: objective 1.536120e+05, 33 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    153612.00000 153612.000  0.00%     -    0s

Explored 1 nodes (33 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 153612 129507 92175 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.536120000000e+05, best bound 1.536120000000e+05, gap 0.0000%

=================== for P=5
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x31882cce
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [5e+00, 5e+00]
Found heuristic solution: objective 93253.000000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 130073.00000

Root relaxation: objective 1.578840e+05, 28 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    157884.00000 157884.000  0.00%     -    0s

Explored 1 nodes (28 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 157884 130073 93253 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.578840000000e+05, best bound 1.578840000000e+05, gap 0.0000%

=================== for P=6
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x72cbbd19
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [6e+00, 6e+00]
Found heuristic solution: objective 93491.000000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 130311.00000

Root relaxation: objective 1.615770e+05, 26 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    161577.00000 161577.000  0.00%     -    0s

Explored 1 nodes (26 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 161577 130311 93491 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.615770000000e+05, best bound 1.615770000000e+05, gap 0.0000%

=================== for P=7
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xed8b0a7b
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [7e+00, 7e+00]
Found heuristic solution: objective 93491.000000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 145336.00000

Root relaxation: objective 1.637110e+05, 23 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    163711.00000 163711.000  0.00%     -    0s

Explored 1 nodes (23 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 163711 145336 93491 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.637110000000e+05, best bound 1.637110000000e+05, gap 0.0000%

=================== for P=8
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x6fba2f2b
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [8e+00, 8e+00]
Found heuristic solution: objective 108080.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 145576.00000

Root relaxation: objective 1.657080e+05, 24 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    165708.00000 165708.000  0.00%     -    0s

Explored 1 nodes (24 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 165708 145576 108080 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.657080000000e+05, best bound 1.657080000000e+05, gap 0.0000%

=================== for P=9
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x7035f7b6
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [9e+00, 9e+00]
Found heuristic solution: objective 119589.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 156952.00000

Root relaxation: objective 1.663460e+05, 24 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    166346.00000 166346.000  0.00%     -    0s

Explored 1 nodes (24 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 166346 156952 119589 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.663460000000e+05, best bound 1.663460000000e+05, gap 0.0000%

=================== for P=10
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0xd11c01cd
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 119589.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 157042.00000

Root relaxation: objective 1.669120e+05, 19 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    166912.00000 166912.000  0.00%     -    0s

Explored 1 nodes (19 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 166912 157042 119589 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.669120000000e+05, best bound 1.669120000000e+05, gap 0.0000%

=================== for P=11
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x7af76ba8
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 119589.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 157074.00000

Root relaxation: objective 1.671520e+05, 18 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167152.00000 167152.000  0.00%     -    0s

Explored 1 nodes (18 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167152 157074 119589 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.671520000000e+05, best bound 1.671520000000e+05, gap 0.0000%

=================== for P=12
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 1966 rows, 1993 columns and 8810 nonzeros
Model fingerprint: 0x4fa1b3b5
Variable types: 0 continuous, 1993 integer (1993 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 3e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 119658.00000
Presolve removed 1928 rows and 1929 columns
Presolve time: 0.00s
Presolved: 38 rows, 64 columns, 195 nonzeros
Variable types: 0 continuous, 64 integer (63 binary)
Found heuristic solution: objective 157103.00000

Root relaxation: objective 1.673460e+05, 10 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    167346.00000 167346.000  0.00%     -    0s

Explored 1 nodes (10 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 167346 157103 119658 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.673460000000e+05, best bound 1.673460000000e+05, gap 0.0000%

boundary = SBC_FD.envelope # .envelope gives you the bounding rectangle of given GeoDataFrame.
boundary.bounds

minx, miny, maxx, maxy = boundary.loc[0].bounds
print(minx, miny, maxx, maxy)

-61331.61300000176 -401270.1777999997 50847.56839999929 -323367.7559000002

from shapely.geometry import Point

# Here, we are going to create fishnet points.
    # Fishnet points are points spaced with an equal interval.
    # You'll see when you see the output!

# Define the interval between points 
#### Note: Adjust interval value as needed for lab question 2
def create_fishnet(interval):
# Create arrays of x and y coordinates using np.arange
    x_coords = np.arange(minx, maxx, interval)
    y_coords = np.arange(miny, maxy, interval)

    # Create a list to store the points
    fishnet_points = []

    # Generate points for the fishnet
    for y in y_coords:
        for x in x_coords:
            fishnet_points.append((x, y))

    # Print the number of points generated
    print("Number of points in the fishnet:", len(fishnet_points))

    fishnet_points = gpd.GeoSeries([Point(pt_cd) for pt_cd in fishnet_points])
    fishnet_points = fishnet_points[fishnet_points.within(SBC_FD.geometry[0])].reset_index()
    fishnet_points.plot(figsize=(15,5))
    return fishnet_points

interval = 5280/5  # default: 5280/5 feet (1 mile / 5 = 0.2 mile) 
fishnet_points = create_fishnet(interval)

Number of points in the fishnet: 7918

# Current Coverage
current_coverage = fishnet_points.within(stations.buffer(S).unary_union).sum()

fishnet_points["weight"] = 1

I = len(fishnet_points)
J = len(stations)
a_i = fishnet_points["weight"]

D_ij = [[np.sqrt((fishnet_points.geometry.x[i] - stations.geometry.x[j])**2 + (fishnet_points.geometry.y[i] - stations.geometry.y[j])**2)
         for j in range(J)] for i in range (I)]

N_i = [[j for j in range(len(D_ij[0])) if D_ij[i][j] <= 8000]
       for i in range (len(D_ij))]

optimize_and_evaluate(demand_block=False)

=================== for P=3
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3305 rows, 3332 columns and 6943 nonzeros
Model fingerprint: 0xe9047901
Variable types: 0 continuous, 3332 integer (3332 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [3e+00, 3e+00]
Found heuristic solution: objective 103.0000000
Presolve removed 3254 rows and 3254 columns
Presolve time: 0.00s
Presolved: 51 rows, 78 columns, 253 nonzeros
Variable types: 0 continuous, 78 integer (78 binary)
Found heuristic solution: objective 289.0000000

Root relaxation: objective 5.400000e+02, 54 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     540.0000000  540.00000  0.00%     -    0s

Explored 1 nodes (54 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 540 289 103 

Optimal solution found (tolerance 1.00e-04)
Best objective 5.400000000000e+02, best bound 5.400000000000e+02, gap 0.0000%

=================== for P=4
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3305 rows, 3332 columns and 6943 nonzeros
Model fingerprint: 0x5c151c55
Variable types: 0 continuous, 3332 integer (3332 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [4e+00, 4e+00]
Found heuristic solution: objective 103.0000000
Presolve removed 3254 rows and 3254 columns
Presolve time: 0.00s
Presolved: 51 rows, 78 columns, 253 nonzeros
Variable types: 0 continuous, 78 integer (78 binary)
Found heuristic solution: objective 446.0000000

Root relaxation: objective 7.040000e+02, 55 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     704.0000000  704.00000  0.00%     -    0s

Explored 1 nodes (55 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 704 446 103 

Optimal solution found (tolerance 1.00e-04)
Best objective 7.040000000000e+02, best bound 7.040000000000e+02, gap 0.0000%

=================== for P=5
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3305 rows, 3332 columns and 6943 nonzeros
Model fingerprint: 0x30b1d761
Variable types: 0 continuous, 3332 integer (3332 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [5e+00, 5e+00]
Found heuristic solution: objective 272.0000000
Presolve removed 3254 rows and 3254 columns
Presolve time: 0.00s
Presolved: 51 rows, 78 columns, 253 nonzeros
Variable types: 0 continuous, 78 integer (78 binary)
Found heuristic solution: objective 564.0000000

Root relaxation: objective 8.550000e+02, 56 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     855.0000000  855.00000  0.00%     -    0s

Explored 1 nodes (56 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 855 564 272 

Optimal solution found (tolerance 1.00e-04)
Best objective 8.550000000000e+02, best bound 8.550000000000e+02, gap 0.0000%

=================== for P=6
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3305 rows, 3332 columns and 6943 nonzeros
Model fingerprint: 0x4d618f48
Variable types: 0 continuous, 3332 integer (3332 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [6e+00, 6e+00]
Found heuristic solution: objective 433.0000000
Presolve removed 3254 rows and 3254 columns
Presolve time: 0.00s
Presolved: 51 rows, 78 columns, 253 nonzeros
Variable types: 0 continuous, 78 integer (78 binary)
Found heuristic solution: objective 725.0000000

Root relaxation: objective 1.005000e+03, 45 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    1005.0000000 1005.00000  0.00%     -    0s

Explored 1 nodes (45 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 1005 725 433 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.005000000000e+03, best bound 1.005000000000e+03, gap 0.0000%

=================== for P=7
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3305 rows, 3332 columns and 6943 nonzeros
Model fingerprint: 0x86f835a6
Variable types: 0 continuous, 3332 integer (3332 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [7e+00, 7e+00]
Found heuristic solution: objective 450.0000000
Presolve removed 3254 rows and 3254 columns
Presolve time: 0.00s
Presolved: 51 rows, 78 columns, 253 nonzeros
Variable types: 0 continuous, 78 integer (78 binary)
Found heuristic solution: objective 891.0000000

Root relaxation: objective 1.146000e+03, 40 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    1146.0000000 1146.00000  0.00%     -    0s

Explored 1 nodes (40 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 1146 891 450 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.146000000000e+03, best bound 1.146000000000e+03, gap 0.0000%

=================== for P=8
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3305 rows, 3332 columns and 6943 nonzeros
Model fingerprint: 0xd0acb5e1
Variable types: 0 continuous, 3332 integer (3332 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [8e+00, 8e+00]
Found heuristic solution: objective 631.0000000
Presolve removed 3254 rows and 3254 columns
Presolve time: 0.00s
Presolved: 51 rows, 78 columns, 253 nonzeros
Variable types: 0 continuous, 78 integer (78 binary)
Found heuristic solution: objective 1045.0000000

Root relaxation: objective 1.270000e+03, 40 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    1270.0000000 1270.00000  0.00%     -    0s

Explored 1 nodes (40 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 1270 1045 631 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.270000000000e+03, best bound 1.270000000000e+03, gap 0.0000%

=================== for P=9
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3305 rows, 3332 columns and 6943 nonzeros
Model fingerprint: 0xfab77a07
Variable types: 0 continuous, 3332 integer (3332 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [9e+00, 9e+00]
Found heuristic solution: objective 780.0000000
Presolve removed 3254 rows and 3254 columns
Presolve time: 0.00s
Presolved: 51 rows, 78 columns, 253 nonzeros
Variable types: 0 continuous, 78 integer (78 binary)
Found heuristic solution: objective 1143.0000000

Root relaxation: objective 1.384000e+03, 34 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    1384.0000000 1384.00000  0.00%     -    0s

Explored 1 nodes (34 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 1384 1143 780 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.384000000000e+03, best bound 1.384000000000e+03, gap 0.0000%

=================== for P=10
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3305 rows, 3332 columns and 6943 nonzeros
Model fingerprint: 0x7479a8cc
Variable types: 0 continuous, 3332 integer (3332 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 780.0000000
Presolve removed 3254 rows and 3254 columns
Presolve time: 0.01s
Presolved: 51 rows, 78 columns, 253 nonzeros
Variable types: 0 continuous, 78 integer (78 binary)
Found heuristic solution: objective 1227.0000000

Root relaxation: objective 1.475000e+03, 35 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    1475.0000000 1475.00000  0.00%     -    0s

Explored 1 nodes (35 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 1475 1227 780 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.475000000000e+03, best bound 1.475000000000e+03, gap 0.0000%

=================== for P=11
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3305 rows, 3332 columns and 6943 nonzeros
Model fingerprint: 0x8bfbba92
Variable types: 0 continuous, 3332 integer (3332 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 790.0000000
Presolve removed 3254 rows and 3254 columns
Presolve time: 0.00s
Presolved: 51 rows, 78 columns, 253 nonzeros
Variable types: 0 continuous, 78 integer (78 binary)
Found heuristic solution: objective 1293.0000000

Root relaxation: objective 1.564000e+03, 32 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    1564.0000000 1564.00000  0.00%     -    0s

Explored 1 nodes (32 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 1564 1293 790 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.564000000000e+03, best bound 1.564000000000e+03, gap 0.0000%

=================== for P=12
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 3305 rows, 3332 columns and 6943 nonzeros
Model fingerprint: 0xf70b3ac7
Variable types: 0 continuous, 3332 integer (3332 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 858.0000000
Presolve removed 3254 rows and 3254 columns
Presolve time: 0.00s
Presolved: 51 rows, 78 columns, 253 nonzeros
Variable types: 0 continuous, 78 integer (78 binary)
Found heuristic solution: objective 1407.0000000

Root relaxation: objective 1.647000e+03, 32 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0    1647.0000000 1647.00000  0.00%     -    0s

Explored 1 nodes (32 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 1647 1407 858 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.647000000000e+03, best bound 1.647000000000e+03, gap 0.0000%

from shapely.geometry import Point

# Here, we are going to create fishnet points.
    # Fishnet points are points spaced with an equal interval.
    # You'll see when you see the output!

# Define the interval between points 
#### Note: Adjust interval value as needed for lab question 2
def create_fishnet(interval):
# Create arrays of x and y coordinates using np.arange
    x_coords = np.arange(minx, maxx, interval)
    y_coords = np.arange(miny, maxy, interval)

    # Create a list to store the points
    fishnet_points = []

    # Generate points for the fishnet
    for y in y_coords:
        for x in x_coords:
            fishnet_points.append((x, y))

    # Print the number of points generated
    print("Number of points in the fishnet:", len(fishnet_points))

    fishnet_points = gpd.GeoSeries([Point(pt_cd) for pt_cd in fishnet_points])
    fishnet_points = fishnet_points[fishnet_points.within(SBC_FD.geometry[0])].reset_index()
    fishnet_points.plot(figsize=(15,5))
    return fishnet_points

interval = 5280/2  # default: 5280/5 feet (1 mile / 5 = 0.2 mile) 
fishnet_points = create_fishnet(interval)

Number of points in the fishnet: 1290

current_coverage = fishnet_points.within(stations.buffer(S).unary_union).sum()

fishnet_points["weight"] = 1

I = len(fishnet_points)
J = len(stations)
a_i = fishnet_points["weight"]

D_ij = [[np.sqrt((fishnet_points.geometry.x[i] - stations.geometry.x[j])**2 + (fishnet_points.geometry.y[i] - stations.geometry.y[j])**2)
         for j in range(J)] for i in range (I)]

N_i = [[j for j in range(len(D_ij[0])) if D_ij[i][j] <= 8000]
       for i in range (len(D_ij))]

optimize_and_evaluate(demand_block=False)

=================== for P=3
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 519 rows, 546 columns and 1103 nonzeros
Model fingerprint: 0xcef4b780
Variable types: 0 continuous, 546 integer (546 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [3e+00, 3e+00]
Found heuristic solution: objective 13.0000000
Presolve removed 485 rows and 488 columns
Presolve time: 0.00s
Presolved: 34 rows, 58 columns, 151 nonzeros
Variable types: 0 continuous, 58 integer (56 binary)
Found heuristic solution: objective 43.0000000

Root relaxation: objective 8.600000e+01, 39 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0      86.0000000   86.00000  0.00%     -    0s

Explored 1 nodes (39 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 86 43 13 

Optimal solution found (tolerance 1.00e-04)
Best objective 8.600000000000e+01, best bound 8.600000000000e+01, gap 0.0000%

=================== for P=4
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 519 rows, 546 columns and 1103 nonzeros
Model fingerprint: 0x6c1b8065
Variable types: 0 continuous, 546 integer (546 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [4e+00, 4e+00]
Found heuristic solution: objective 13.0000000
Presolve removed 485 rows and 488 columns
Presolve time: 0.00s
Presolved: 34 rows, 58 columns, 151 nonzeros
Variable types: 0 continuous, 58 integer (56 binary)
Found heuristic solution: objective 67.0000000

Root relaxation: objective 1.130000e+02, 35 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     113.0000000  113.00000  0.00%     -    0s

Explored 1 nodes (35 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 113 67 13 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.130000000000e+02, best bound 1.130000000000e+02, gap 0.0000%

=================== for P=5
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 519 rows, 546 columns and 1103 nonzeros
Model fingerprint: 0x0edd7bb0
Variable types: 0 continuous, 546 integer (546 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [5e+00, 5e+00]
Found heuristic solution: objective 39.0000000
Presolve removed 485 rows and 488 columns
Presolve time: 0.00s
Presolved: 34 rows, 58 columns, 151 nonzeros
Variable types: 0 continuous, 58 integer (56 binary)
Found heuristic solution: objective 86.0000000

Root relaxation: objective 1.380000e+02, 33 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     138.0000000  138.00000  0.00%     -    0s

Explored 1 nodes (33 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 138 86 39 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.380000000000e+02, best bound 1.380000000000e+02, gap 0.0000%

=================== for P=6
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 519 rows, 546 columns and 1103 nonzeros
Model fingerprint: 0x7ec0d3f0
Variable types: 0 continuous, 546 integer (546 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [6e+00, 6e+00]
Found heuristic solution: objective 64.0000000
Presolve removed 485 rows and 488 columns
Presolve time: 0.00s
Presolved: 34 rows, 58 columns, 151 nonzeros
Variable types: 0 continuous, 58 integer (56 binary)
Found heuristic solution: objective 111.0000000

Root relaxation: objective 1.610000e+02, 35 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     161.0000000  161.00000  0.00%     -    0s

Explored 1 nodes (35 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 161 111 64 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.610000000000e+02, best bound 1.610000000000e+02, gap 0.0000%

=================== for P=7
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 519 rows, 546 columns and 1103 nonzeros
Model fingerprint: 0xc0c56a2c
Variable types: 0 continuous, 546 integer (546 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [7e+00, 7e+00]
Found heuristic solution: objective 67.0000000
Presolve removed 485 rows and 488 columns
Presolve time: 0.00s
Presolved: 34 rows, 58 columns, 151 nonzeros
Variable types: 0 continuous, 58 integer (56 binary)
Found heuristic solution: objective 114.0000000

Root relaxation: objective 1.840000e+02, 29 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     184.0000000  184.00000  0.00%     -    0s

Explored 1 nodes (29 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 184 114 67 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.840000000000e+02, best bound 1.840000000000e+02, gap 0.0000%

=================== for P=8
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 519 rows, 546 columns and 1103 nonzeros
Model fingerprint: 0x42f51dea
Variable types: 0 continuous, 546 integer (546 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [8e+00, 8e+00]
Found heuristic solution: objective 95.0000000
Presolve removed 485 rows and 488 columns
Presolve time: 0.01s
Presolved: 34 rows, 58 columns, 151 nonzeros
Variable types: 0 continuous, 58 integer (56 binary)
Found heuristic solution: objective 138.0000000

Root relaxation: objective 2.040000e+02, 22 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     204.0000000  204.00000  0.00%     -    0s

Explored 1 nodes (22 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 204 138 95 

Optimal solution found (tolerance 1.00e-04)
Best objective 2.040000000000e+02, best bound 2.040000000000e+02, gap 0.0000%

=================== for P=9
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 519 rows, 546 columns and 1103 nonzeros
Model fingerprint: 0xa05648d8
Variable types: 0 continuous, 546 integer (546 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [9e+00, 9e+00]
Found heuristic solution: objective 119.0000000
Presolve removed 485 rows and 488 columns
Presolve time: 0.00s
Presolved: 34 rows, 58 columns, 151 nonzeros
Variable types: 0 continuous, 58 integer (56 binary)
Found heuristic solution: objective 169.0000000

Root relaxation: objective 2.210000e+02, 26 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     221.0000000  221.00000  0.00%     -    0s

Explored 1 nodes (26 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 221 169 119 

Optimal solution found (tolerance 1.00e-04)
Best objective 2.210000000000e+02, best bound 2.210000000000e+02, gap 0.0000%

=================== for P=10
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 519 rows, 546 columns and 1103 nonzeros
Model fingerprint: 0x9694b029
Variable types: 0 continuous, 546 integer (546 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 119.0000000
Presolve removed 485 rows and 488 columns
Presolve time: 0.00s
Presolved: 34 rows, 58 columns, 151 nonzeros
Variable types: 0 continuous, 58 integer (56 binary)
Found heuristic solution: objective 182.0000000

Root relaxation: objective 2.360000e+02, 22 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     236.0000000  236.00000  0.00%     -    0s

Explored 1 nodes (22 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 236 182 119 

Optimal solution found (tolerance 1.00e-04)
Best objective 2.360000000000e+02, best bound 2.360000000000e+02, gap 0.0000%

=================== for P=11
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 519 rows, 546 columns and 1103 nonzeros
Model fingerprint: 0x53e70d3e
Variable types: 0 continuous, 546 integer (546 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 120.0000000
Presolve removed 485 rows and 488 columns
Presolve time: 0.00s
Presolved: 34 rows, 58 columns, 151 nonzeros
Variable types: 0 continuous, 58 integer (56 binary)
Found heuristic solution: objective 208.0000000

Root relaxation: objective 2.480000e+02, 23 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     248.0000000  248.00000  0.00%     -    0s

Explored 1 nodes (23 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 248 208 120 

Optimal solution found (tolerance 1.00e-04)
Best objective 2.480000000000e+02, best bound 2.480000000000e+02, gap 0.0000%

=================== for P=12
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (mac64[arm] - Darwin 22.1.0 22A400)

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 519 rows, 546 columns and 1103 nonzeros
Model fingerprint: 0xde16faa2
Variable types: 0 continuous, 546 integer (546 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+01, 1e+01]
Found heuristic solution: objective 131.0000000
Presolve removed 485 rows and 488 columns
Presolve time: 0.00s
Presolved: 34 rows, 58 columns, 151 nonzeros
Variable types: 0 continuous, 58 integer (56 binary)
Found heuristic solution: objective 212.0000000

Root relaxation: objective 2.600000e+02, 20 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     260.0000000  260.00000  0.00%     -    0s

Explored 1 nodes (20 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 3: 260 212 131 

Optimal solution found (tolerance 1.00e-04)
Best objective 2.600000000000e+02, best bound 2.600000000000e+02, gap 0.0000%

	OBJECTID	County	FDID	MACSID	Name	Address	City	Zip	FireChief	Phone	Notes	LastUpdate	Website	CALFIREUni	SHAPE_Leng	SHAPE_Area	geometry
0	89	KERN	15010	KRN	KERN CO FD	5642 VICTOR ST	BAKERSFIELD	93308	AARON DUNCAN	(661) 391‐7000	None	2018-06-21	https://kerncountyfire.org/	KRN	998841.649563	1.921083e+10	MULTIPOLYGON (((207559.325 -315382.144, 207622...
1	304	SAN LUIS OBISPO	40080	SLC	SAN LUIS OBISPO CO FD	635 N SANTA ROSA ST	SAN LUIS OBISPO	93405	JOHN OWENS	(805) 543‐4244	None	2018-06-21	https://calfireslo.org/	SLU	940256.942591	8.344077e+09	MULTIPOLYGON (((-58528.672 -319737.906, -58473...
2	316	SANTA BARBARA	42005	CRP	CARPINTERIA SUMMERLAND FPD	1140 EUGENE PLACE, SUITE A	CARPINTERIA	93013	GREG FISH	(805) 684‐4591	None	2018-06-21	https://www.carpfire.com/	SBC	49534.138992	1.010901e+08	POLYGON ((50973.663 -398386.099, 50969.942 -39...
3	317	SANTA BARBARA	42030	MTO	MONTECITO FPD	595 SAN YSIDRO RD	SANTA BARBARA	93108	KEVIN TAYLOR	(805) 969‐7762	None	2018-06-21	https://www.montecitofire.com/	SBC	39911.074682	3.644463e+07	POLYGON ((35557.315 -399389.055, 35295.841 -39...
4	318	SANTA BARBARA	42035	SBC	SANTA BARBARA CFD	4410 CATHEDRAL OAKS RD	SANTA BARBARA	93110	MARK A. HARTWIG	(805) 681‐5500	None	2018-06-21	https://www.sbcfire.com/	SBC	778360.396807	3.666998e+09	MULTIPOLYGON (((23728.804 -401033.857, 23715.3...
5	396	VENTURA	56020	VNC	VENTURA COUNTY FPD	165 DURLEY AVE	CAMARILLO	93010	DUSTIN GARDNER	(805) 389‐9710	None	2018-06-21	https://vcfd.org/	VNC	840086.616548	4.239353e+09	MULTIPOLYGON (((72888.961 -429800.719, 72849.7...
6	647	SANTA BARBARA	42010	GUA	GUADALUPE FD	918 OBISPO ST	GUADALUPE	93434	MICHAEL CASH	(805) 356‐3905	None	2022-02-10	https://ci.guadalupe.ca.us/fire/	SBC	14598.470583	3.446183e+06	POLYGON ((-52159.523 -337901.424, -52142.953 -...
7	662	SANTA BARBARA	42040	SMR	SANTA MARIA FD	314 WEST COOK ST #8	SANTA MARIA	93458	TODD TUGGLE	(805) 925‐0951	None	2022-02-14	https://www.cityofsantamaria.org/city-governme...	SBC	71542.884890	6.075262e+07	MULTIPOLYGON (((-36710.959 -344913.125, -36707...
8	676	SANTA BARBARA	42025	STB	SANTA BARBARA CITY FD	925 CHAPALA ST	SANTA BARBARA	93101	CHRIS MAILES	(805) 965‐5254	None	2022-02-14	https://www.santabarbaraca.gov/gov/depts/fire/...	SBC	81431.348424	5.056587e+07	MULTIPOLYGON (((15469.272 -397501.519, 15472.5...
9	678	SANTA BARBARA	42015	LMP	LOMPOC FD	115 SOUTH G ST	LOMPOC	93436	BRIAN FALLON	(805) 736‐4513	None	2022-02-14	https://www.cityoflompoc.com/government/depart...	SBC	38950.291184	3.025921e+07	MULTIPOLYGON (((-42597.382 -377627.460, -42626...

	Label	Desig	Number	Type	Department	Name_other	Address	Notes	Num_2019	Scale	Latitude	Longitude	geometry
0	VAFB-41	AFV-1	41	Fire Station	Vandenberg Fire Department	None	Airfield Rd., Vandenberg, CA	None	41	0	34.7342	-120.569	POINT (-52075.698 -364541.170)
1	VAFB-42	AFV-2	42	Fire Station	Vandenberg Fire Department	None	New Mexico Ave., Vandenberg, CA	None	42	0	34.7345	-120.534	POINT (-48865.923 -364526.814)
2	VAFB-44	AFV-4	44	Fire Station	Vandenberg Fire Department	None	Arguello Rd., Vandenberg, CA	None	44	0	34.6125	-120.570	POINT (-52227.109 -378048.804)
3	VAFB-45	AFV-5	45	Fire Station	Vandenberg Fire Department	None	Lasalle Canyon Rd., Vandenberg, CA	None	45	0	34.6496	-120.614	POINT (-56277.374 -373901.714)
4	SBC-31	SBC-31	31	Fire Station	Santa Barbara County Fire Department	None	168 W Hwy 246, Buellton, CA 93427	None	31	900	34.6132	-120.197	POINT (-18043.064 -378107.359)
...	...	...	...	...	...	...	...	...	...	...	...	...	...
203	LAC-143	LAC-143	143	Fire Station	LAC	None	None	None	None	0	34.4545	-118.634	POINT (125491.361 -394834.163)
204	VNC-Saticoy	VNC-Saticoy	0	Fire Station	VNC	None	None	None	None	0	34.3115	-119.134	POINT (79681.290 -411244.355)
205	VNC-27	VNC-27	27	Fire Station	VNC	None	None	None	None	0	34.3935	-118.928	POINT (98577.520 -401948.877)
206	VNC-85	VNC-85	85	Fire Station	VNC	None	None	None	None	0	34.1862	-118.930	POINT (98645.842 -424951.021)
207	KRN-58	KRN-58	58	Fire Station	KRN	None	None	None	None	0	34.8523	-119.169	POINT (75904.018 -351258.013)

Lab 4: Fire Service Coverage Analysis - Maximal Covering Location Problem¶

Step 1. Prepare your dataset¶

Task: Load the three datasets and convert blocks and stations crs into the same one as FDs.crs.¶

Task: Look into the following Fire District maps.¶

Question 1: Sort out a Fire District out of FDs GeoDataFrame. The district must have its 'Name" column value, "SANTA BARBARA CFD". ( 1 pt )¶

Task: Run following cell, "del FDs". Note: It will delete FDs variable.¶

Task: take a subset of stations, within SBC_FD.¶

Question 2: Plot the blocks GeoDataFrame. ( 2 pts )¶

Step 2. Conduct MCLP¶

Task: Based on the mathematical Model, set the I and J values correctly.¶

Task: We are going to have block's population as weight assigned to demand. Define $a_i$.¶

Task: Create $D_{ij}$ variable using Euclidean Distance between demand $i$ and facility $j$.¶

Question 3: Create $N_i$ variable in list format. ( 1 pt )¶

Question 4: Complete the Optimization Model ( 6 pts )¶

Question 5: Take a subset of stations based on the model output. ( 1 pt )¶

Question 6: Plot the open_stations and their coverage buffers with the demand buffers. ( 2 pts )¶

Step 3. Functionize / Modularize¶

Question 7: Functionize your code out of Question 4 and 5 ( 2 pts )¶

Step 4. Evaluate the Result¶

Question 8: To evaluate the optimization result, we always compare with the current operation. Calculate current_coverage. ( 2 pts )¶

Task: Check if provided code works with your defined function, solve_mclp¶

Task: Check if the output Table is plausible. And learn how to create a pandas DataFrame¶

Task: Put your code to plot open_stations and coverage buffer from Question 6.¶

Task: Following function is to go through the whole process. Check if you get the same output as before :)¶

¶

Task: Review from Lab 2. We are creating fishnet points within the SBC_FD¶

Question 9: Re-compute the model variables here for fishnet_points, instead of blocks. ( 1 pt )¶

Task: Repeat the whole process with another fishnet_points with different fishnet interval.¶

Question 10: Compare the Scatter plots out of Blocks, 0.2 mile fishnet points, and another fishnet points with interval of your choice. Discuss the insights you can get. ( 5 pts )¶

	P	Coverage
0	3	142059.0
1	4	153612.0
2	5	157884.0
3	6	161577.0
4	7	163711.0
5	8	165708.0
6	9	166346.0
7	10	166912.0
8	11	167152.0
9	12	167346.0
10	13	167465.0
11	14	167535.0
12	15	167604.0
13	16	167618.0
14	17	167619.0
15	18	167619.0
16	19	167619.0
17	20	167619.0
18	21	167619.0
19	22	167619.0
20	23	167618.0
21	24	167619.0
22	25	167619.0
23	26	167619.0
24	27	167619.0
25	28	167619.0